public class offer36
{
    public int InversePairs(int[] array)
    {
        if (array == null || array.length <= 1)
            return 0;
        int[] temp = new int[array.length];
        int re;
        int mid = (array.length - 1) / 2;
        re = merge(array, temp, 0, mid, array.length - 1);
        return re;
    }

    public int merge(int[] array, int[] temp, int start, int mid, int end)
    {
        if (end <= start)
            return 0;
        int lmid, rmid;
        lmid = start + (mid - start) / 2;
        rmid = mid + 1 + (end - mid - 1) / 2;
        int lcount, rcount;
        lcount = merge(array, temp, start, lmid, mid);
        rcount = merge(array, temp, mid + 1, rmid, end);

        int l = mid;
        int r = end;
        int p = end;
        int max;
        int count = 0;
        while (true)
        {
            if (l < start || r < mid + 1)
                break;
            max = array[r];
            r--;
            if (max < array[l])
            {
                max = array[l];
                r++;
                l--;
                count += r - mid;
            }
            temp[p] = max;
            p--;
        }
        while (l >= start)
        {
            temp[p] = array[l];
            p--;
            l--;
        }
        while (r >= mid + 1)
        {
            temp[p] = array[r];
            p--;
            r--;
        }

        int i;
        for (i = start; i <= end; i++)
            array[i] = temp[i];
        count = count + rcount + lcount;

        return count;
    }

}